---
title: "Lake Counting S"
created: 2025-11-28
tags:
  - 算法
---

# Lake Counting S

## 题目 [Lake Counting S](https://www.luogu.com.cn/problem/P1596)

![[image-3ad234ad.png]]

## 思路分析

![[image-86209f50.png]]

![[image-90033379.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=110;

char g[N][N];

bool st[N][N];

int n,m,res;

int dx[8]={-1,-1,0,1,1,1,0,-1};

int dy[8]={0,1,1,1,0,-1,-1,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];

}

void dfs(int x,int y){

	for(int i=0;i<8;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && g[nx][ny]=='W'){

			st[nx][ny]=true;

			dfs(nx,ny);

			//只能用一次 不能回溯

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<n;i++){

		cin>>g[i];

	}

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			if(g[i][j]=='W' && !st[i][j]){

				dfs(i,j);

				res++;

			}

		}

	}

	cout<<res<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[Flood Fill 连通块|Flood Fill 连通块]] 🏠 [[00-刷题理模型]] ➡️ [[城堡问题|城堡问题]]